package com.hyb.algorithm.data.struct.window;

import java.util.*;

/**
 * @Author: huyanbing
 * @Date: 2021/9/5 11:21 上午
 * <p>
 * 239. 滑动窗口最大值
 * <p>
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class MaxSlidingWindow {


    public static void main(String[] args) {

        //int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int[] nums = new int[]{7,2,4};


        MaxSlidingWindow exe = new MaxSlidingWindow();
        int[] res=exe.maxSlidingWindow(nums, 2);

        for(int i=0;i<res.length;i++){
            System.out.print(","+res[i]);
        }

    }

    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;

        int[] res = new int[len - k + 1];
        MonotonicQueue monotonicQueue = new MonotonicQueue();

        int index = 0;
        for (int i = 0; i < len; i++) {
            if (i < k - 1) {
                //先填满窗口的 前k-1
                monotonicQueue.push(nums[i]);
            } else {
                //向前滑动
                monotonicQueue.push(nums[i]);
                res[index] = monotonicQueue.max();

                index++;
                //滑出
                monotonicQueue.pop(nums[i - k + 1]);
            }
        }

        return res;
    }

    class MonotonicQueue {

        /**
         * 单调递减队列
         */
        Deque<Integer> deque = new ArrayDeque<>();

        public void push(int n) {
            while (!deque.isEmpty() && deque.peekLast() < n) {
                deque.pollLast();
            }

            deque.addLast(n);
        }


        public int max() {
            return deque.peekFirst();
        }

        public void pop(int n) {
            if (!deque.isEmpty() && deque.peekFirst() == n) {
                deque.pollFirst();
            }
        }
    }
}
